FINE PRECISION ESTIMATION OF BOOLEAN FORMULAS’ COMPLEXITY IN SOME BASES CONSISTING OF GATES WITH DIRECT AND ITERATIVE INPUTS

Lozhkin Sergey Andreevich, Doctor of physical and mathematical sciences, professor, sub-department of mathematical cybernetics, Lomonosov Moscow State University (1 Leninskie Gory street, Moscow, Russia), lozhkin@cs.msu.ru
Konovodov Vladimir Aleksandrovich, Postgraduate student, Lomonosov Moscow State University (1 Leninskie Gory street, Moscow, Russia), vkonovodov@gmail.com

519.714

Background. One of the main problems in mathematical cybernetics is the problem of control systems synthesis, consisting in building of a circuit from the given class that will realize the given function of logic algebra. At solving of the problem one often needs to take into account various limitations of control systems’ structure and parameters. Such limitations often describe real calculations more precisely, and the research of function complexity in models with limitation is of great theoretical interest. In the present work the limitation is associated with methods of gates connection in a circuit. Circuit gates’ inputs are divided into 2 types – direct and iterative. Iterative inputs are used for connection of other gates’ outputs to them, and direct inputs serve as circuits’ inputs. The synthesis problem in this model is considered for a case of formulas, i.e. circuits without gates’ inputs branching. The aim of the work is to estimate the Shannon function of fine precision for formulas’ complexity in some complete bases of the given type, i.e. the estimates that reveal asymptotics of the second term of asymptotic expansion of the said function. Earlier there has only been obtained the asymptotics of the Shannon function for bases, iterative bridging of which includes a class of monotonic functions; estimates of fine precision for wide basis classes in the present model haven’t been revealed.
Materials and methods. In this work in particular the authors show the modification of the previously known optimal method of formulas synthesis using the technique of logic-algebra functions modeling by variables on components of special partitions of multiple sets of the Boolean cube. These structures are based on the building of special formulas that realize functions, having gate partitions of multiple own variables with constant entropy.
Results. The authors obtained estimates of fine precision of the Shannon function for formulas complexity of logic algebra in some complete bases with direct and iterative variables, iterative bridging of which includes a class of monotonic functions.
Conclusions. For the first time in the class of formulas in bases with direct and iterative inputs there has been singled out quite a wide sub-class, in which there has been obtained the estimates of fine precision of the Shannon function for complexity thereof.

Boolean formulas, direct and iterative variables, synthesis, complexity, Shannon function, asymptotic estimates of fine precision.

1. Lozhkin S. A. Vestnik Moskovskogo universiteta. Ser. 15. Vychislitel'naya matematika i kibernetika [Bulletin of Moscow University. Series 15. Calculus mathematics and cybernetics]. 1999, no. 3, pp. 35–41.
2. Lozhkin S. A. Diskretnye modeli v teorii upravlyayushchikh sistem: tr. III Mezhdunar. konf. (Krasnovidovo, 22–28 iyunya 1998 g.) [Discrete models in the control system theory: proceedings of III International conference (Krasnovidovo, 22-28 June 1998)]. Moscow: Dialog-MGU, 1998, pp. 72–73.
3. Lozhkin S. A., Konovodov V. A. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Fiziko-matematicheskie nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2015, no. 1 (31), pp. 55–68.
4. Konovodov V. A. Uchenye zapiski Kazanskogo universiteta. Ser. Fizikomatematicheskie nauki [Proceedings of Kazan Uiversity . Series: Physical and mathematical sciences]. 2014, vol. 156, no. 3, pp. 76–83.
5. Yablonskiy S. V. Vvedenie v diskretnuyu matematiku [Introduction into discrete mathematics]. Moscow: Nauka, 1986, 384 p.
6. Lozhkin S. A. Lektsii po osnovam kibernetiki [Lectures on basic cybernetics]. Moscow: MAKS Press,2004,256p.
7. Lozhkin S. A. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. 1996, no. 6, pp. 189–213.
8. Lozhkin S. A. Vestnik Moskovskogo universiteta. Ser. 1. Matematika i mekhanika [Bulletin of Moscow University. Series 1. Mathematics and mechanics]. 2007, no. 3, pp. 19–25.